package pl.mmadej.ds4java.ds.tree.binary.splay;

import pl.mmadej.ds4java.ds.tree.binary.BinaryTreeNode;
import pl.mmadej.ds4java.ds.tree.binary.bst.BinarySearchTree;


public class SplayTree<T extends Comparable<T>> extends BinarySearchTree<T> {

    @Override
    protected void afterNodeAdded(BinaryTreeNode<T> newNode) {
        super.afterNodeAdded(newNode);
        splayUp(newNode);
    }

    @Override
    protected void afterNodeAccessed(BinaryTreeNode<T> accessedNode) {
        super.afterNodeAccessed(accessedNode);
        splayUp(accessedNode);
    }

    private void splayUp(BinaryTreeNode<T> node) {
        while (shouldSplayUp(node)) {
            if (shouldDoRightZigWithRoot(node)) {
                rotateRight(root);
            } else if (shouldDoLeftZigWithRoot(node)) {
                rotateLeft(root);
            } else if (shouldDoRightRightZigZigWithGrandfather(node)) {
                rotateRight(node.getParent().getParent());
                rotateRight(node.getParent());
            } else if (shouldDoLeftLeftZigZigWithGrandfather(node)) {
                rotateLeft(node.getParent().getParent());
                rotateLeft(node.getParent());
            } else if (leftChildOfParent(node)) {
                //right left zig zag
                rotateRight(node.getParent());
                rotateLeft(node.getParent());
            } else {
                //left right zig zag
                rotateLeft(node.getParent());
                rotateRight(node.getParent());
            }
        }
    }

    private boolean shouldDoRightRightZigZigWithGrandfather(BinaryTreeNode<T> node) {
        return node.getParent().getLeftChild() == node && node.getParent().getParent().getLeftChild() == node.getParent();
    }

    private boolean shouldDoLeftLeftZigZigWithGrandfather(BinaryTreeNode<T> node) {
        return node.getParent().getRightChild() == node && node.getParent().getParent().getRightChild() == node.getParent();
    }

    private boolean leftChildOfParent(BinaryTreeNode<T> node) {
        return node.getParent().getLeftChild() == node;
    }

    private boolean shouldDoLeftZigWithRoot(BinaryTreeNode<T> newNode) {
        return root.getRightChild() == newNode;
    }

    private boolean shouldDoRightZigWithRoot(BinaryTreeNode<T> newNode) {
        return root.getLeftChild() == newNode;
    }

    private boolean shouldSplayUp(BinaryTreeNode<T> node) {
        return node != root;
    }
}
